#include "../exercise.h"

// TODO: 改正函数实现，实现正确的缓存优化斐波那契计算
// THINk: 这个函数是一个纯函数（pure function）吗？
// READ: 纯函数 <https://zh.wikipedia.org/wiki/%E7%BA%AF%E5%87%BD%E6%95%B0>
static unsigned long long fibonacci(int i) {
    // TODO: 为缓存设置正确的初始值
    static unsigned long long cache[96] = {0, 1}; // 初始化前两项
    static int cached = 1; // 当前已经计算到的最大索引（从0开始，所以1表示已经计算到索引1）

    // 如果i大于当前已缓存的索引，需要继续计算
    if (i > cached) {
        // 从cached+1开始计算直到i
        for (int j = cached + 1; j <= i; ++j) {
            cache[j] = cache[j-1] + cache[j-2];
        }
        cached = i; // 更新已缓存的最大索引
    }
    return cache[i];
}

// ---- 不要修改以下代码 ----
int main(int argc, char **argv) {
    ASSERT(fibonacci(0) == 0, "fibonacci(0) should be 0");
    ASSERT(fibonacci(1) == 1, "fibonacci(1) should be 1");
    ASSERT(fibonacci(2) == 1, "fibonacci(2) should be 1");
    ASSERT(fibonacci(3) == 2, "fibonacci(3) should be 2");
    ASSERT(fibonacci(10) == 55, "fibonacci(10) should be 55");

    auto fib90 = fibonacci(90);
    std::cout << "fibonacci(90) = " << fib90 << std::endl;
    ASSERT(fib90 == 2880067194370816120, "fibonacci(90) should be 2880067194370816120");
    return 0;
}
/*
static真好用，初始化一次后不会再被初始化，但是可以被赋值，所以可以这样写

这个函数不是纯函数（pure function）。

原因分析：
1. 有状态（Stateful）
函数使用了静态变量 cache 和 cached，这些变量在多次函数调用之间保持状态：

第一次调用 fibonacci(3) 时，会计算并缓存前4项（0,1,1,2）
第二次调用 fibonacci(2) 时，直接返回缓存的值，不进行任何计算
2. 引用透明性（Referential Transparency）破坏
纯函数要求相同的输入总是产生相同的输出，但这个函数的输出可能依赖于调用历史：

// 假设这是程序的第一次调用
fibonacci(5); // 计算并缓存前6项

// 后续调用相同的参数，但行为不同
fibonacci(3); // 直接返回缓存值，不进行计算
虽然数学上 fibonacci(3) 总是等于2，但函数的执行过程和副作用（修改静态变量）在不同调用中是不同的。

3. 有副作用（Side Effects）
函数修改了静态变量 cache 和 cached，这是明显的副作用。纯函数不应该修改任何外部状态。

这样可以在同一个代码中，多次调用函数，时间复杂度降到比原本的O（n）还要小，原本的动态规划：

```
unsigned long long fibonacci_pure(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    unsigned long long a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}
```

每次调用都是O（n）
*/